package com.codingvip.graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author hansongtao
 */
public class Graph {
    //顶点的个数
    private int v;
    //邻接表
    private LinkedList<Integer> adj[];

    public Graph(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }

    }


    public static Graph init(int v) {
        Graph graph = new Graph(v);
        graph.addEdge(0, 1);
        graph.addEdge(0, 3);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(2, 5);
        graph.addEdge(3, 4);
        graph.addEdge(4, 5);
        return graph;
    }

    public static void main(String[] args) {
        Graph graph = Graph.init(6);
//        graph.topoSortByDFS();
        graph.topSortBykahn();

    }




    /**
     * Return the length of the shortest path between root and target node.
     */
//    int BFS(Node root, Node target) {
//        Queue<Node> queue;  // store all nodes which are waiting to be processed
//        Set<Node> used;     // store all the used nodes
//        int step = 0;       // number of steps neeeded from root to current node
//        // initialize
//        add root to queue;
//        add root to used;
//        // BFS
//        while (queue is not empty) {
//            step = step + 1;
//            // iterate the nodes which are already in the queue
//            int size = queue.size();
//            for (int i = 0; i < size; ++i) {
//                Node cur = the first node in queue;
//                return step if cur is target;
//                for (Node next : the neighbors of cur) {
//                    if (next is not in used) {
//                        add next to queue;
//                        add next to used;
//                    }
//                }
//                remove the first node from queue;
//            }
//        }
//        return -1;          // there is no path from root to target
//    }

    public void addEdge(int s, int t) {
        adj[s].add(t);
    }

    public void topSortBykahn() {
        //统计每个结点的入度
        int[] inDegree = new int[v];
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < adj[i].size(); j++) {
                //i->w
                int w = adj[i].get(j);
                inDegree[w]++;

            }
        }
        for (int i = 0; i < v; i++) {
            System.out.println("==>" + inDegree[i]);
        }
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < v; ++i) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
        while (!queue.isEmpty()) {
            int i = queue.remove();
            System.out.println("->" + i);
            for (int j = 0; j < adj[i].size(); j++) {
                int k = adj[i].get(j);
                inDegree[k]--;
                if (inDegree[k] == 0) {
                    queue.add(k);
                }
            }
        }
    }

    public void topoSortByDFS() {
        //先构建逆邻接表，边s->t 表示，s依赖于t,t先于s；
        LinkedList<Integer> inversedAdj[] = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            inversedAdj[i] = new LinkedList<>();

        }
        //通过邻接表生成逆邻接表
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < adj[i].size(); j++) {
                //i->w
                int w = adj[i].get(j);
                //w->i
                inversedAdj[w].add(i);
            }
        }
        boolean[] visited = new boolean[v];
        for (int i = 0; i < v; i++) {
            if (visited[i] == false) {
                visited[i] = true;
                dfs(i, inversedAdj, visited);
            }
        }

    }



    private void dfs(int vertex, LinkedList<Integer>[] inversedAdj, boolean[] visited) {
        for (int i = 0; i < inversedAdj[vertex].size(); i++) {
            int w = inversedAdj[vertex].get(i);
            if (visited[w] == true) {
                continue;
            }
            visited[w] = true;
            dfs(w, inversedAdj, visited);
        }

        System.out.println("->" + vertex);
    }
}
